#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : IntersectionTwoArrays.py
# @Time    : 2020/11/2 10:03
# @Description:
from typing import List


class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """
        Given two arrays, write a function to compute their intersection.

        Example 1:
            Input: nums1 = [1,2,2,1], nums2 = [2,2]
            Output: [2]
        Example 2:
            Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
            Output: [9,4]
        Note:
            - Each element in the result must be unique.
            - The result can be in any order.

        :param nums1:
        :param nums2:
        :return:
        """
        nums1.sort()
        nums2.sort()

        length1, length2 = len(nums1), len(nums2)

        ans = []
        index1 = index2 = 0
        while index1 < length1 and index2 < length2:
            num1 = nums1[index1]
            num2 = nums2[index2]
            if num1 == num2:
                if not ans or num1 != ans[-1]:
                    ans.append(num1)
                index1 += 1
                index2 += 1
            elif num1 < num2:
                index1 += 1
            else:
                index2 += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    nums1 = [1, 2, 2, 1]
    nums2 = [2, 2]
    print(S.intersection(nums1, nums2))
    print('done')
